#
# @lc app=leetcode.cn id=41 lang=python3
#
# [41] 缺失的第一个正数
#

# @lc code=start
from typing import List


class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        n = len(nums)
        for i, j in enumerate(nums):
            if j <= 0:
                nums[i] = n + 1
        for j in nums:
            if 1 <= abs(j) <= n:
                nums[abs(j) - 1] = -abs(nums[abs(j) - 1])
        for i, j in enumerate(nums):
            if j >= 0:
                return i + 1
        return n + 1


if __name__ == '__main__':
    s = Solution()
    firstMissingPositive = s.firstMissingPositive

    print(firstMissingPositive([1, 2, 0]) == 3)
    print(firstMissingPositive([3, 4, -1, 1]) == 2)
    print(firstMissingPositive([7, 8, 9, 11, 12]) == 1)
# @lc code=end
